package com.gaogzhen.algorithms4.sort;

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;


/**
 * 插入排序
 * 思想：希尔排序的思想是使任意间隔h的元素都是有序的。这样的数组被称为h有序数组。
 * 算法：
 * 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 * 按增量序列个数k，对序列进行k 趟排序；
 * 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
 */
public class MergeBU {

    private static Comparable[] aux;

    /**
     * 排序方法
     * @param a     实现了Comparable接口的待排序数组
     */
    public static void sort(Comparable[] a) {
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz) {
            for (int lo = 0; lo < N -sz; lo += sz + sz) {
                merge(a, lo, lo + sz -1, Math.min(lo + sz + sz - 1, N -1));
            }
        }
    }

    /**
     * 归并以排序的两个子数组
     * @param a         数组
     * @param lo        子数组1起始索引
     * @param mid       子数组1终止索引，mid+1子数组2起始索引
     * @param hi        子数组2终止索引
     */
    private static void merge(Comparable[] a, int lo, int mid, int hi) {
        // 将a[lo...mid]和a[mid+1...hi]归并
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        for (int k = lo; k <= hi; k++) {
            if (i > mid) a[k] = aux[j++];
            else if (j > hi) a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else a[k] = aux[i++];
        }
    }

    /**
     * 比较大小
     * @param a     目标a
     * @param b     目标b
     * @return      返回布尔值
     */
    private static  boolean less(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }

    /**
     * 交换数组元素
     * @param a     数组
     * @param i     索引
     * @param j     索引
     */
    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    /**
     * 打印数组
     * @param a     数组
     */
    private static void show(Comparable[] a) {
        // 单行打印数组
        for (int i = 0; i < a.length; i++) {
            StdOut.print(a[i] + " ");
        }
        StdOut.println();
    }

    /**
     * 测试数组是否已经有序
     * @param a     带测试数组
     * @return      测试结果: true-数组有序；false-数组无序
     */
    public static boolean isSorted(Comparable[] a) {
        // 测试数组是否已经有序
        for (int i = 1; i < a.length; i++) {
            if (less(a[i], a[i-1])) return false;
        }
        return  true;
    }

    public static void main(String[] args) {
        // 从标准输入读取字符串，将他们排序并输出
        String[] a = StdIn.readAllStrings();
        sort(a);
        assert isSorted(a);
        show(a);
    }
}
